134. 加油站

Similar Question

Solution Tips

方案一: 暴力法 + 模拟

var canCompleteCircuit = function(gas, cost) {
    // 方案一: 寻找可能的起点, 然后直接出发, 如果不行就回溯
    for (let i = 0; i < gas.length; i++) {
        let start = i;
        let rest = 0;
        let j = i;
        while (true) {
            // 可以去到下一站
            if (cost[j] <= gas[j] + rest) {
                rest = rest + gas[j] - cost[j];
                if (rest < 0) {
                    break;
                }
                j = (j + 1) % gas.length;
                if (j === start) {
                    return start;
                }
            }
            else {
                // 去不到下一站
                break;
            }
        }
    }
    return -1;
    // 暴力法超时了, 直接看总汽油数和总cost数? 如果相等就可以到达?
    // 1 0 2 vs 1 1 1
    // 如果可以到达, 那么直接从油量和cost最大的出发? 保存最多的油量出发即可
};

方案二: 贪心

直观理解，不用公式推导。可以这样想：假设从 x 加油站出发经过 z 加油站最远能到达 y 加油站，那么从 z 加油站直接出发，不可能到达 y 下一个加油站。因为从 x 出发到 z 加油站时肯定还有存储的油，这都到不了 y 的下一站，而直接从 z 出发刚开始是没有存储的油的，所以更不可能到达 y 的下一站。

var canCompleteCircuit = function(gas, cost) {
    const n = gas.length;
    let i = 0;
    while (i < n) {
        let sumOfGas = 0, sumOfCost = 0;
        let cnt = 0;
        while (cnt < n) {
            const j = (i + cnt) % n;
            sumOfGas += gas[j];
            sumOfCost += cost[j];
            if (sumOfCost > sumOfGas) {
                break;
            }
            cnt++;
        }
        if (cnt === n) {
            return i;
        } else {
            i = i + cnt + 1;
        }
    }
    return -1;
};